/* -*- mode: c++; c-file-style: raknet; tab-always-indent: nil; -*- */
/*
  NEW AND IMPROVED EFFICIENT Queue ADT - By Kevin Jenkins
  Initilize with the following structure
  Queue<TYPE, OPTIONAL INITIAL ALLOCATION SIZE>
 
  Has the following member functions
  push - adds an element to the top of the queue
  pop - returns the bottom element from the queue and removes it.  Result undefined if queue empty
  peek - returns the bottom element from the queue.  Result undefined if queue empty
  size - returns the size of the queue
  compress - reallocates memory to fit the number of elements. Best used when the number of elements decreases
  clear - empties the queue and returns storage
  find - returns bool if the specified element is in the queue
  The assignment and copy constructors are defined
 
  EXAMPLE
  Queue<int, 20> A;
  A.push(5);
  A.push(10);
 
  A.peek(); // Returns 5
  A.pop(); // Returns 5
  A.peek(); // Returns 10
  A.pop();  // Returns 10
// At this point the queue is empty
 
NOTES
The default initial allocation size is 1
This function doubles the amount of memory allocated when the queue is filled
This is better than the linked list version for a queue that doesn't go from one extreme to the other with size changes.
 
9/04 Giblet - commented out body of compress() function, as it is invalid and breaks newer compilers
 
*/


#ifndef __QUEUE_H
#define __QUEUE_H

// Template classes have to have all the code in the header file
#include <assert.h>

namespace BasicDataStructures
{
	template <class queue_type>
	
	class Queue
	{
	
	public:
		Queue();
		~Queue();
		Queue( Queue& original_copy );
		bool operator= ( const Queue& original_copy );
		void push( const queue_type& input );
		void pushAtHead( const queue_type& input );
		queue_type& operator[] ( unsigned long position ); // Not a normal thing you do with a queue but can be used for efficiency
		void del( unsigned long position ); // Not a normal thing you do with a queue but can be used for efficiency
		inline const queue_type peek( void ) const;
		inline const queue_type pop( void );
		inline const unsigned long size( void ) const;
		inline void clear( void );
		void compress( void );
		bool find ( queue_type q );
		void clearAndForceAllocation( int size ); // Force a memory allocation to a certain larger size
		
	private:
		queue_type* array;
		unsigned long head;  // Array index for the head of the queue
		unsigned long tail; // Array index for the tail of the queue
		unsigned long allocation_size;
	};
	
	
	template <class queue_type>
	inline const unsigned long Queue<queue_type>::size( void ) const
	{
		if ( head <= tail )
			return tail -head;
		else
			return allocation_size -head + tail;
	}
	
	template <class queue_type>
	Queue<queue_type>::Queue()
	{
		allocation_size = 16;
		array = new queue_type[ allocation_size ];
		head = 0L;
		tail = 0L;
	}
	
	template <class queue_type>
	Queue<queue_type>::~Queue()
	{
		clear();
	}
	
	template <class queue_type>
	inline const queue_type Queue<queue_type>::pop( void )
	{
#ifdef _DEBUG
		assert( allocation_size > 0 && size() >= 0L );
		assert( head != tail );
#endif
		//head=(head+1) % allocation_size;
		
		if ( ++head == allocation_size )
			head = 0;
			
		if ( head == 0 )
			return ( queue_type ) array[ allocation_size -1 ];
			
		return ( queue_type ) array[ head -1 ];
	}
	
	template <class queue_type>
	void Queue<queue_type>::pushAtHead( const queue_type& input )
	{
		if ( allocation_size == 0L )
		{
			array = new queue_type[ 16 ];
			head = 0L;
			tail = 1L;
			array[ 0 ] = input;
			allocation_size = 16L;
			return ;
		}
		
		if ( head == 0 )
			head = allocation_size - 1;
		else
			--head;
			
		array[ head ] = input;
		
		if ( tail == head )
		{
			//  unsigned long index=tail;
			
			// Need to allocate more memory.
			queue_type * new_array;
			new_array = new queue_type[ allocation_size * 2L ];
#ifdef _DEBUG
			
			assert( new_array );
#endif
			
			for ( unsigned long counter = 0L; counter < allocation_size; ++counter )
				new_array[ counter ] = array[ ( head + counter ) % ( allocation_size ) ];
				
			head = 0L;
			
			tail = allocation_size;
			
			allocation_size *= 2L;
			
			// Delete the old array and move the pointer to the new array
			delete [] array;
			
			array = new_array;
		}
	}
	
	
	template <class queue_type>
	inline const queue_type Queue<queue_type>::peek( void ) const
	{
#ifdef _DEBUG
		assert( head != tail );
		assert( allocation_size > 0 && size() >= 0L );
#endif
		
		return ( queue_type ) array[ head ];
	}
	
	template <class queue_type>
	void Queue<queue_type>::push( const queue_type& input )
	{
		if ( allocation_size == 0L )
		{
			array = new queue_type[ 16 ];
			head = 0L;
			tail = 1L;
			array[ 0 ] = input;
			allocation_size = 16L;
			return ;
		}
		
		array[ tail++ ] = input;
		
		if ( tail == allocation_size )
			tail = 0;
			
		if ( tail == head )
		{
			//  unsigned long index=tail;
			
			// Need to allocate more memory.
			queue_type * new_array;
			new_array = new queue_type[ allocation_size * 2L ];
#ifdef _DEBUG
			
			assert( new_array );
#endif
			
			for ( unsigned long counter = 0L; counter < allocation_size; ++counter )
				new_array[ counter ] = array[ ( head + counter ) % ( allocation_size ) ];
				
			head = 0L;
			
			tail = allocation_size;
			
			allocation_size *= 2L;
			
			// Delete the old array and move the pointer to the new array
			delete [] array;
			
			array = new_array;
		}
		
	}
	
	template <class queue_type>
	Queue<queue_type>::Queue( Queue& original_copy )
	{
		// Allocate memory for copy
		
		if ( original_copy.size() == 0L )
		{
			allocation_size = 0L;
		}
		
		else
		{
			array = new queue_type [ original_copy.size() + 1 ];
			
			for ( unsigned long counter = 0L; counter < original_copy.size(); ++counter )
				array[ counter ] = original_copy.array[ ( original_copy.head + counter ) % ( original_copy.allocation_size ) ];
				
			head = 0L;
			
			tail = original_copy.size();
			
			allocation_size = original_copy.size() + 1;
		}
	}
	
	template <class queue_type>
	bool Queue<queue_type>::operator= ( const Queue& original_copy )
	{
		if ( ( &original_copy ) == this )
			return false;
			
		clear();
		
		// Allocate memory for copy
		if ( original_copy.size() == 0L )
		{
			allocation_size = 0L;
		}
		
		else
		{
			array = new queue_type [ original_copy.size() + 1 ];
			
			for ( unsigned long counter = 0L; counter < original_copy.size(); ++counter )
				array[ counter ] = original_copy.array[ ( original_copy.head + counter ) % ( original_copy.allocation_size ) ];
				
			head = 0L;
			
			tail = original_copy.size();
			
			allocation_size = original_copy.size() + 1;
		}
		
		return true;
	}
	
	template <class queue_type>
	inline void Queue<queue_type>::clear ( void )
	{
		if ( allocation_size == 0L )
			return ;
			
		delete[] array;
		
		allocation_size = 0L;
		
		head = 0L;
		
		tail = 0L;
	}
	
	template <class queue_type>
	void Queue<queue_type>::compress ( void )
	{
		/*queue_type* new_array;
		
		if (allocation_size==0) return;
		
		new_array = new queue_type [size()+1];
		 
		array = new queue_type [original_copy.size()];
		
		for (unsigned long counter=0L; counter < size(); ++counter)
		array[counter] = original_copy.array[(head + counter)%(allocation_size)];
		
		allocation_size=original_copy.size();
		 
		head=0L;
		tail=size();
		 
		// Delete the old array and move the pointer to the new array
		delete []array;
		array=new_array;*/
	}
	
	template <class queue_type>
	bool Queue<queue_type>::find ( queue_type q )
	{
		if ( allocation_size == 0 )
			return false;
			
		unsigned int counter = head;
		
		while ( counter != tail )
		{
			if ( array[ counter ] == q )
				return true;
				
			counter = ( counter + 1 ) % allocation_size;
		}
		
		return false;
	}
	
	template <class queue_type>
	void Queue<queue_type>::clearAndForceAllocation( int size )
	{
		delete [] array;
		array = new queue_type[ size ];
		allocation_size = size;
		head = 0L;
		tail = 0L;
	}
	
	template <class queue_type>
	inline queue_type& Queue<queue_type>::operator[] ( unsigned long position )
	{
#ifdef _DEBUG
		assert( position < size() );
#endif
		//return array[(head + position) % allocation_size];
		
		if ( head + position >= allocation_size )
			return array[ head + position - allocation_size ];
		else
			return array[ head + position ];
	}
	
	template <class queue_type>
	void Queue<queue_type>::del( unsigned long position )
	{
#ifdef _DEBUG
		assert( position < size() );
		assert( head != tail );
#endif
		
		if ( head == tail || position >= size() )
			return ;
			
		unsigned long index;
		
		unsigned long next;
		
		//index  = (head + position) % allocation_size;
		if ( head + position >= allocation_size )
			index = head + position - allocation_size;
		else
			index = head + position;
			
		//next = (index + 1) % allocation_size;
		next = index + 1;
		
		if ( next == allocation_size )
			next = 0;
			
		while ( next != tail )
		{
			// Overwrite the previous element
			array[ index ] = array[ next ];
			index = next;
			//next = (next + 1) % allocation_size;
			
			if ( ++next == allocation_size )
				next = 0;
		}
		
		// Move the tail back
		if ( tail == 0 )
			tail = allocation_size - 1;
		else
			--tail;
	}
} // End namespace

#endif

